|
In graph theory, a weak coloring is a special case of a graph labeling. A weak -coloring of a graph assigns a color to each vertex , such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated , there is a vertex with and . The figure on the right shows a weak 2-coloring of a graph. Each dark vertex (color 1) is adjacent to at least one light vertex (color 2) and vice versa. ==Properties== A graph vertex coloring is a weak coloring, but not necessarily vice versa. Every graph has a weak 2-coloring. The figure on the right illustrates a simple algorithm for constructing a weak 2-coloring in an arbitrary graph. Part (a) shows the original graph. Part (b) shows a breadth-first search tree of the same graph. Part (c) shows how to color the tree: starting from the root, the layers of the tree are colored alternatingly with colors 1 (dark) and 2 (light). If there is no isolated vertex in the graph , then a weak 2-coloring determines a domatic partition: the set of the nodes with is a dominating set, and the set of the nodes with is another dominating set. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Weak coloring」の詳細全文を読む スポンサード リンク
|